package org.shj.algorithm.string;

/**
 * 假设一个排序数组（没有重复元素）以某个未知元素作为支点进行旋转， 如： 原数组
 * 是 0， 1， 2， 4， 5， 6， 7 旋转后的数组是： 4， 5， 6， 7， 0， 1， 2
 * 求旋转后数组中的最小元素
 *
 * 思路： 二分查找的一种变体，因为以支点为分隔的前后两个数组是有序的, 较小的
 * 序列肯定在后面。
 *
 * @author Shen Huang Jian
 * @date 2019-01-17 18:24
 */
public class MinRotate {

    public static void main(String[] args){
        int[] rotatedArr = new int[]{ 3, 4, 5, 6, 7, 0, 1, 2};

        int low = 0;
        int high = rotatedArr.length - 1;
        int ind = 0;

        boolean found = false;
        while (!found){
            int mid = (low + high) / 2;
            if(rotatedArr[mid] > rotatedArr[mid + 1]){
                ind = mid + 1;
                found = true;

            }else {
                if(rotatedArr[mid] < rotatedArr[mid - 1]){
                    found = true;
                    ind = mid;
                }else if(rotatedArr[mid] > rotatedArr[high]){
                    low = mid;
                }else {
                    high = mid;
                }
            }
        }

        System.out.println(rotatedArr[ind]);
    }
}
